`
https://leetcode.cn/problems/implement-router/
`

/**
 * @param {number} memoryLimit
 */
var Router = function (memoryLimit) {
  this.limit = memoryLimit
  this.packetQ = new Queue() // 存储数据包的队列
  this.packetSet = new Set() // 存储数据包的集合，方便去重
  // 使用数组模拟队列，再维护一个 head 表示队头
  this.destToTimestamps = new Map() // destination -> [[timestamp, ...], head]
};

/** 
 * @param {number} source 
 * @param {number} destination 
 * @param {number} timestamp
 * @return {boolean}
 */
Router.prototype.addPacket = function (source, destination, timestamp) {
  const key = `${source},${destination},${timestamp}`
  // 已经有相同类型的包了
  if (this.packetSet.has(key)) return false
  // 记录包
  this.packetSet.add(key)
  // 查看是否满了
  if (this.packetQ.size() === this.limit) {
    this.forwardPacket()
  }
  // 存包
  this.packetQ.enqueue([source, destination, timestamp])
  if (!this.destToTimestamps.has(destination)) {
    this.destToTimestamps.set(destination, [[], 0])
  }
  this.destToTimestamps.get(destination)[0].push(timestamp)
  return true
};

/**
 * @return {number[]}
 */
Router.prototype.forwardPacket = function () {
  if (this.packetQ.isEmpty()) return []
  // 拿到最旧的数据包，发出
  const [source, destination, timestamp] = this.packetQ.dequeue()
  this.packetSet.delete(`${source},${destination},${timestamp}`)
  this.destToTimestamps.get(destination)[1]++ // 队头下标 +1 ，模拟出队
  return [source, destination, timestamp]
};

/** 
 * @param {number} destination 
 * @param {number} startTime 
 * @param {number} endTime
 * @return {number}
 */
Router.prototype.getCount = function (destination, startTime, endTime) {
  // 根本没有到 destination 的数据包
  if (!this.destToTimestamps.has(destination)) return 0
  const [timestamps, head] = this.destToTimestamps.get(destination)
  // 找到第一个 >= startTime 的位置
  const left = lower_bound(timestamps, startTime, { left: head - 1 })
  // 找到第一个 > endTime 的位置
  const right = lower_bound(timestamps, endTime + 1, { left: head - 1 })
  return right - left
};

/** 
 * Your Router object will be instantiated and called as such:
 * var obj = new Router(memoryLimit)
 * var param_1 = obj.addPacket(source,destination,timestamp)
 * var param_2 = obj.forwardPacket()
 * var param_3 = obj.getCount(destination,startTime,endTime)
 */

function lower_bound(arr, target, { mapFn, left = -1, right = arr.length } = {}) {
  const targetVal = typeof mapFn === 'function' ? mapFn(target) : target
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    const midVal = typeof mapFn === 'function' ? mapFn(arr[mid]) : arr[mid]
    midVal < targetVal ? left = mid : right = mid
  }
  return right
}